//////////////////////////////////////
// Fast Container Library           //
// MIT License - Copyright (c) 2012 //
//////////////////////////////////////

#pragma once

#include "vector_map.h"


FC_NAMESPACE_BEGIN


template<class Key, class Value, class Compare, class Allocator>
class vector_multimap : public vector_map<Key, Value, Compare, Allocator>
{
public:
	typedef vector_map<Key, Value, Compare, Allocator>		base_type;
	typedef vector_multimap<Key, Value, Compare, Allocator>	this_type;
	typedef typename base_type::key_type					key_type;
	typedef typename base_type::mapped_type					mapped_type;
	typedef typename base_type::key_compare					key_compare;
	typedef typename base_type::value_compare				value_compare;
	typedef typename base_type::size_type					size_type;
	typedef typename base_type::value_type					value_type;
	typedef typename base_type::iterator					iterator;
	typedef typename base_type::const_iterator				const_iterator;
	typedef typename base_type::reverse_iterator			reverse_iterator;
	typedef typename base_type::const_reverse_iterator		const_reverse_iterator;
	typedef typename base_type::allocator_type				allocator_type;

	using base_type::begin;
	using base_type::end;
	using base_type::rbegin;
	using base_type::rend;
	using base_type::size;
	using base_type::empty;
	using base_type::capacity;
	using base_type::get_allocator;
	using base_type::set_allocator;
	using base_type::erase_at;
	using base_type::clear;
	using base_type::data;
	using base_type::front;
	using base_type::back;
	using base_type::reserve;
	using base_type::set_capacity;
	using base_type::shrink_to_fit;
	using base_type::iterator_is_valid;
	using base_type::swap;
	using base_type::erase;
	using base_type::lower_bound;
	using base_type::upper_bound;
	using base_type::find;
	using base_type::key_comp;
	using base_type::value_comp;
	using base_type::operator =;

	explicit vector_multimap()
		: base_type()
		{
		}

	explicit vector_multimap( const allocator_type& alloc )
		: base_type(alloc)
		{
		}

	explicit vector_multimap( const Compare& compare, const allocator_type& alloc = allocator_type() )
		: base_type(compare, alloc)
		{
		}

	template <class InputIterator>
	vector_multimap( InputIterator first, InputIterator last, const Compare& compare = Compare(), const allocator_type& alloc = allocator_type() )
		: base_type(compare, alloc)
		{
			insert(first, last);
			sort();
		}

	vector_multimap( const this_type& x)
		: base_type(x)
		{
		}

	iterator insert( const value_type& value )
	{
		iterator it = upper_bound( value.first );
		return base_type::base_type::insert( it, value );
	}

	iterator insert( iterator it, const value_type& value )
	{
		it = lower_bound( value.first );
		return base_type::insert( it, value );
	}

	template <class Iter>
	void insert( Iter first, Iter last )
	{
		base_type::base_type::insert( begin(), first, last );
		sort();
	}

	size_t erase( const key_type& key )
    {
		pair<iterator, iterator> it = equal_range(key);
		base_type::erase(it.first, it.second);
		return size_type(it.second - it.first);
	}

	size_t count( const key_type& key ) const
	{
		pair<const_iterator, const_iterator> it = equal_range(key);
		return size_type(it.second - it.first);
	}

	pair<iterator, iterator> equal_range( const key_type& key )
	{
		iterator first = lower_bound(key);
		iterator last = first;
		while( last != end() && !base_type::m_compare(key, *++last) ) ;
		return pair<iterator, iterator>(first, last);
	}

	pair<const_iterator, const_iterator> equal_range( const key_type& key ) const
	{
		const_iterator first = lower_bound(key);
		const_iterator last = first;
		while( last != end() && !base_type::m_compare(key, *++last) ) ;
		return pair<const_iterator, const_iterator>(first, last);
	}

	void sort()
	{
		if( size() > (size_type)1 )
			fc::sort( begin(), end(), base_type::m_compare );
	}

};



FC_NAMESPACE_END

